package com.mc.search;

//二叉查找树
public class BST<Key extends Comparable<Key>,Value> {
	private Node root;
	private class Node{
		private Key key;
		private Value val;
		private Node left;
		private Node right;
		private int N;
		public Node(Key key,Value val,int N){
			this.key = key;
			this.val = val;
			this.N = N;
		}
	}
	public int size(){
		return size(root);
	}
	private int size(Node node){
		if(node==null)return 0;
		return node.N;
	}
	public Value get(Key key){
		return get(root,key);
	}
	private Value get(Node node,Key key){
		if(node==null)
			return null;
		else if(node.key.compareTo(key)==0)
			return node.val;
		else if(node.key.compareTo(key)==-1)
			return get(node.right,key);
		else
			return get(node.left,key);
	}
	public void put(Key key,Value val){
		put(root,key,val);
	}
	private Node put(Node node,Key key,Value val){
		if(node==null)
		{
			node = new Node(key,val,1);
			return node;
		}
		int cmp = key.compareTo(node.key);
		if(cmp<0)
			node.left = put(node.left,key,val);
		else if(cmp>0)
			node.right = put(node.right,key,val);
		else
			node.val = val;
		node.N = size(node.left)+size(node.right)+1;//递归更新节点计数
		return node;
	}
	public Key min(){
		return min(root).key;
	}
	private Node min(Node node){
		if(node.left==null)
			return node;
		return min(node.left);
	}
	public Key max(){
		return max(root).key;
	}
	private Node max(Node node){
		if(node.right==null)
			return node;
		return max(node.right);
	}
	public Key select(int k){
		return select(root,k);
	}
	private Key select(Node node,int k){
		if(node==null)return null;
		int t = size(node.left);
		if(t>k)
			return select(node.left,k);
		else if(t<k)
			return select(node.right,k-t-1);
		else
			return node.key;
	}
	public int rank(Key key){
		return rank(root,key);
	}
	private int rank(Node node,Key key){
		if(node==null)return 0;
		int cmp = key.compareTo(node.key);
		if(cmp==0)
			return size(node.left);
		else if(cmp<0)
			return rank(node.left,key);
		else
			return 1+size(node.left)+rank(node.right,key);
	}
	public void deleteMin(){
		root = deleteMin(root);
	}
	private Node deleteMin(Node node){
		if(node.left==null)
			return node.right;
		node.left = deleteMin(node.left);
		node.N = size(node.left)+size(node.right)+1;
		return node;
	}
	public void delete(Key key){
		root= delete(root,key);
	}
	private Node delete(Node node, Key key){
		if(node==null)return null;
		int cmp = key.compareTo(node.key);
		if(cmp<0) node.left = delete(node.left,key);
		else if(cmp>0) node.right = delete(node.right,key);
		else{
			if(node.right==null)return node.left;
			if(node.left==null)return node.right;
			Node min = min(node.right);
			min.right= deleteMin(node.right);
			min.left = node.left;
		}
		node.N = size(node.left)+size(node.right)+1;
		return node;
	}
}
